174. Dungeon Game.go

package leetcode

import"math"

// 解法一 动态规划
funccalculateMinimumHP(dungeon [][]int) int {
iflen(dungeon) ==0 {
return0
 }
m, n:=len(dungeon), len(dungeon[0])
dp:=make([][]int, m)
fori:=0; i<m; i++ {
dp[i] =make([]int, n)
 }
dp[m-1][n-1] =max(1-dungeon[m-1][n-1], 1)
fori:=n-2; i>=0; i-- {
dp[m-1][i] =max(1, dp[m-1][i+1]-dungeon[m-1][i])
 }
fori:=m-2; i>=0; i-- {
dp[i][n-1] =max(1, dp[i+1][n-1]-dungeon[i][n-1])
 }
fori:=m-2; i>=0; i-- {
forj:=n-2; j>=0; j-- {
dp[i][j] =min(max(1, dp[i][j+1]-dungeon[i][j]), max(1, dp[i+1][j]-dungeon[i][j]))
 }
 }
returndp[0][0]
}

funcmax(aint, bint) int {
ifa>b {
returna
 }
returnb
}

funcmin(aint, bint) int {
ifa>b {
returnb
 }
returna
}

// 解法二 二分搜索
funccalculateMinimumHP1(dungeon [][]int) int {
low, high:=1, math.MaxInt64
forlow<high {
mid:=low+ (high-low)>>1
ifcanCross(dungeon, mid) {
high=mid
 } else {
low=mid+1
 }
 }
returnlow
}

funccanCross(dungeon [][]int, startint) bool {
m, n:=len(dungeon), len(dungeon[0])
dp:=make([][]int, m)
fori:=0; i<m; i++ {
dp[i] =make([]int, n)
 }
fori:=0; i<len(dp); i++ {
forj:=0; j<len(dp[i]); j++ {
ifi==0&&j==0 {
dp[i][j] =start+dungeon[0][0]
 } else {
a, b:=math.MinInt64, math.MinInt64
ifi>0&&dp[i-1][j] >0 {
a=dp[i-1][j] +dungeon[i][j]
 }
ifj>0&&dp[i][j-1] >0 {
b=dp[i][j-1] +dungeon[i][j]
 }
dp[i][j] =max(a, b)
 }
 }
 }
returndp[m-1][n-1] >0
}